﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GKS.Extensions.String.PatternMatching {
    
    /// <summary>
    /// A class that contains the implementation of the Z Algorithm. 
    /// For more information regarding the algorithm visit: http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/zalg.pdf
    /// </summary>
    public static class ZAlgorithm {

        /// <summary>
        /// The implementation of the Z Algorithm. 
        /// </summary>
        /// <param name="text">The text in which we have to search the wanted pattern.</param>
        /// <param name="pattern">The pattern that we want to search for.</param>
        /// <param name="numberOfComparisons">The number of comparisons executed by the algorithm.</param>
        /// <returns>The indexes of the occurrences of the pattern in the text.</returns>
        /// <remarks>
        ///     The default connection character in this method is '$'. 
        ///     In case this character appears in one of the strings (the text or the pattern) please use 
        ///     the other method where you can specify a character that does not appear neither in the text nor in the pattern.
        /// </remarks>
        public static int[] ZAlgorithmImplementation(this string text, string pattern, out int numberOfComparisons) {
            return text.ZAlgorithmImplementation(pattern, '$', out numberOfComparisons);
        }

        /// <summary>
        /// The implementation of the Z Algorithm.
        /// </summary>
        /// <param name="text">The text in which we have to search the wanted pattern.</param>
        /// <param name="pattern">The pattern that we want to search for.</param>
        /// <param name="connectionChar">
        ///     A character that does not appear neither in the text nor in the pattern. 
        ///     For the correct execution of the algorithm this character MUST NOT APPEAR neither in the text nor in the pattern.
        /// </param>
        /// <param name="numberOfComparisons">The number of comparisons executed by the algorithm.</param>
        /// <returns>The indexes of the occurrences of the pattern in the text.</returns>
        public static int[] ZAlgorithmImplementation(this string text, string pattern, char connectionChar, out int numberOfComparisons) {
            List<int> occurrencesIndexes = new List<int>();
            string finalText = string.Format("{0}{1}{2}", pattern, connectionChar, text);
            var preprocessingResult = finalText.ZAlgorithmPreprocessing(out numberOfComparisons);
            int[] z = preprocessingResult["z"];
            int pLength = pattern.Length + 1;

            for (int i = 0; pLength + i < z.Length; i++) {
                if (z[pLength + i] == pattern.Length) {
                    occurrencesIndexes.Add(i);
                }
            }

            return occurrencesIndexes.ToArray();
        }

        /// <summary>
        /// The preprocessing of this string.
        /// </summary>
        /// <param name="text">The text that has to be preprocessed.</param>
        /// <param name="numberOfComparisons">The number of comparisons executed by the preprocessing.</param>
        /// <returns>The result of the preprocessing, the sizes of the z-boxes, the starting indexes of the z-boxes, and the last indexes of the z-boxes.</returns>
        public static Dictionary<string, int[]> ZAlgorithmPreprocessing(this string text, out int numberOfComparisons) {
            int[] z = new int[text.Length],     // the z sizes for each position
                  r = new int[text.Length],     // the r indexes for each z-box
                  l = new int[text.Length];     // the l indexes for each z-box
            int j, k, m;
            numberOfComparisons = 0;

            // initializing the values of each r and each l to -1
            for (m = 0; m < text.Length; m++) {
                r[m] = -1;
                l[m] = -1;
            }

            // preprocessing the string
            for (j = 1; j < text.Length; j++) {
                m = 0;
                k = j;

                if (k > r[k - 1]) {
                    // compare character starting from position k with characters starting from position 0
                    // stop when a mismatch is found

                    while (k < text.Length && text.ElementAt(k).Equals(text.ElementAt(m++))) {
                        numberOfComparisons++;
                        z[j]++;
                        k++;
                    }

                    if (k < text.Length) { numberOfComparisons++; }

                    if (z[j] > 0) {
                        r[j] = j + z[j] - 1;

                        if (r[j] > r[j - 1]) {
                            l[j] = j;
                        } else {
                            r[j] = r[j - 1];
                            l[j] = l[j - 1];
                        }
                    }
                } else {    // k < r[i-1]
                    // k is in a z-box
                    int k1 = k - l[j - 1];

                    if (z[k1] - 1 < r[j - 1] - k) {
                        // z[k1] < |Beta|
                        // z[k1] < (r-k)
                        z[k] = z[k1];
                        r[k] = r[k - 1];
                        l[k] = l[k - 1];
                    } else {
                        // z[k1] > |Beta|
                        // z[k1] > (r-k)
                        int q = r[j - 1] + 1;
                        int q1 = r[j - 1] - k + 1;// l[j - 1];

                        if (q < text.Length) {
                            while (q < text.Length && text.ElementAt(q).Equals(text.ElementAt(q1++))) {
                                numberOfComparisons++;
                                q++;
                            }

                            z[k] = q - k;
                            r[k] = q - 1;
                            l[k] = k;
                        } else {
                            z[k] = z[k1];
                            r[k] = r[k - 1];
                            l[k] = l[k - 1];
                        }
                    }
                }
            }

            return new Dictionary<string, int[]>() {
                { "z", z },
                { "r", r },
                { "l", l }
            };
        }
    }
}
